1. Origin of the Invention:
The invention described herein was made in the performance of work under a NASA contract, and is subject to the provisions of Public Law 96-517 (35 USC 202) in which the Contractor has elected not to retain title.
2. Technical Field:
The invention relates to parallel processing arrays and in particular to the application of such arrays to optimum path planning from a starting point to a destination point across a known terrain, and the selection of the optimum path from plural paths.
3. Background of the Invention:
A number of techniques are known in the art for performing path planning. U.S. Pat. No. 4,812,990 employs a "least cost" methodology to path plan, but is a software implementation of mathematical optimization algorithms, and therefore suffers from the disadvantages of being complex and time consuming and requiring large computer resources to implement it. Its method of "weighing" costs relies on the mathematical algorithms and has nothing to do with the "time" delay costs of the present invention.
U.S. Pat. No. 4,570,227 teaches determining the optimum path using a comparator circuit which compares all possible routes. It does not use time delay propagation to measure cost. It also has no ability to scale the cost because it cannot distinguish between a shorter path that is uphill and more time consuming with one that is longer but on a flat grade. Moreover, it is not capable of multiple destination point analysis.
U.S. Pat. No. 4,862,373 provides a method for determining the shortest collision free path through a 3-D space utilizing a set of pre-stored 2-D maps at different altitudes. However, it relies on software implementations of mathematical optimization algorithms, and therefore requires significant computer support hardware. It cannot scale costs and cannot perform multiple destination point analysis.
C. R. Carroll, "A Neural Processor for Maze Solving", Analog VLSI Implementation of Neural Systems, Kluwer Academic Publishers, Boston (1989) discloses a 4.times.4 array of binary processors allowing for a 2-state "cost scaling" and a 4.times.8 array for 3-state "cost-scaling". This technique therefore provides a very limited dynamic range of cost scaling for path planning.
Accordingly, it is an object of the invention to perform high speed optimum path planning requiring no software or computer support during operation.
It is a further object of the invention to perform such path planning with many levels (e.g., 256) of programmable costs at each cell in an array representing terrain to be crossed.
It is a yet further object of the invention to perform such path planning on a high speed integrated circuit.
It is a still further object of the invention to perform such path planning simultaneously for multiple destination points.